In order to improve the performance of computing systems, caches are often implemented. A computing system can involve a single cache or tiered cache levels. Further, the cache can be large. For example, a computing system may use a flash cache to cache data. An index may be used to track the data stored in the flash cache. The index may associate a location of the data with an identifier of the data. When data is accessed (e.g., read or written), the index is consulted using a lookup operation. Because a flash cache can be large, the index may also be large. Unfortunately, maintaining a large index consumes a significant portion of memory. Systems and methods are needed to implement a low-overhead index for a cache such as a flash cache.